package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * 81. 搜索旋转排序数组 II
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/23 9:38
 */
public class Search81 {

    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int index = findMin(nums);
        int length = nums.length;
        int st = 0;
        int end = length - 1;
        while (st <= end) {
            int m = st + ((end - st) >> 1);
            int v = m + index;
            int m1 = v >= length ? v - length : v;
            if (nums[m1] == target) {
                return true;
            }
            if (nums[m1] > target) {
                end = m - 1;
            } else {
                st = m + 1;
            }
        }
        return false;
    }

    private int findMin(int[] nums) {
        int st = 0;
        int end = nums.length - 1;
        while (st < end) {
            int last = nums[end];
            int m = st + ((end - st) >>> 1);
            if (nums[m] > last) {
                st = m + 1;
            } else if (nums[m] < last) {
                end = m;
            } else {
                for (int i = st; i <= end; i++) {
                    if (i != 0 && nums[i - 1] > nums[i]) {
                        return i;
                    }
                }
                return st;
            }
        }
        return st;
    }

}
